💛 前情提要💛

本章节是数据结构的二叉树重要面试OJ题的相关知识~

接下来我们即将进入一个全新的空间，对代码有一个全新的视角~

以下的内容一定会让你对数据结构有一个颠覆性的认识哦！！！

❗以下内容以C语言的方式实现，对于数据结构来说最重要的是思想哦❗

以下内容干货满满，跟上步伐吧~

二叉树的层序遍历

二叉树重要面试OJ题

🔥算法思想

💡广度优先遍历： 对于二叉树来说又称为层序遍历

❗特别注意：

对于广度优先遍历，我们一般借助队列的数据结构去实现【对于>队列head = pq->tail = NULL;}void QueueDestroy(Queue* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}}QDataType QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}QDataType QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}int QueueSize(Queue* pq){assert(pq);QNode* cur = pq->head;int size = 0;while (cur){++size;cur = cur->next;}return size;}

2️⃣实现层序遍历：

✨综上：就是层序遍历啦~

➡️相信大家对新的遍历方式有不一样的看法了吧🧡

❗ 秒杀口诀：

❓忘记的同学可以>点击网站跳转left) + treeSize(root->right) + 1;}void preorder(struct TreeNode* root, int*arr, int* i){//前序遍历if (root == NULL){return;}arr[(*i)++] = root->val;preorder(root->left, arr, i);preorder(root->right, arr, i);}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = treeSize(root);int* arr = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;preorder(root, arr, &i);return arr;}

➡️补充：

我们需要带着自己开辟的数组和数组下标进行前序遍历，因为需要将遍历得到的结点存入数组中

所以每一次下标的改变都需要让不同的递归栈帧知道，所以下标需要传的是地址（否则如果传的是下标的临时拷贝，那数组内的结点之间就会造成覆盖）

:mag:题目传送门：

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树

示例 1：

示例 2：

💡解题关键：

遍历主树的每一个结点，让每一个结点当作根节点时，去判断此时的根节点的树是否与子树相同

此时我们便可以复用检查两棵树是否相同的代码进行判断

👉秒杀分析：

因为需要遍历主树的每一个结点，让其每一个结点当根节点时的树去与子树判断是否相同

所以我们对主树采取前序遍历【即这样遍历下，我们可以快速且从上往下全面的判断是否为子树】，若为其余遍历方式，则可能一开始就错过导致程序做了一些无用功

又因为只要主树里一旦找到为子树的情况，就无需继续找子树了，所以逻辑关系为||【即主树的某个结点为树时是子树的情况，返回true，逻辑关系||遇上true就可以直接停止寻找】

➡️做题思路：

用前序遍历遍历主树每一个结点，让每一个结点当作根节点去作树，与需要判断的子树判断两棵树是否相同

一旦找到，就返回true，停止寻找

✊动图示例：

👉代码实现：

:mag:题目传送门：

给定一个二叉树，判断它是否是高度平衡的二叉树

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1

💡解题关键：

👉秒杀分析：

对于树中的每一个结点为根节点看作一棵树时，都需要时刻满足平衡条件，所以逻辑关系采用&&【即递归判断子树是否平衡时，只要一个不满足返回false，那整体就直接停止判断并返回false表示不平衡】

而遍历树中每一个结点时，我们采用前序遍历，这样一旦判断当前不满足平衡条件，就不需要判断后面的了

综上，秒杀口诀为：&&➕前序遍历

❗特别注意：

对于获取二叉树最大深度，我们采用的秒杀口诀为：后序遍历➕比较获取最大深度

在比较获取最大深度中，+1表示所获取子树的层数加上当前树的根节点的这一层

✊动图示例：

👉代码实现：

❗此题曾为清华大学OJ题，同学们一定要细心感受这一道题目哟❗

:mag:题目传送门：

🌐